#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <unordered_set>

using namespace std;

// 2014. 重复 K 次的最长子序列
// https://leetcode.cn/problems/longest-subsequence-repeated-k-times/description/?envType=daily-question&envId=2025-06-27

class Solution
{
    string ans;
    int mk;
    unordered_set<string> strSet;

    bool isSubqueue(string &mainStr, string &str)
    {
        int mLen = mainStr.size();
        int subLen = str.size();
        if (mLen < subLen)
        {
            return false;
        }
        int j = 0;
        int k = mk;
        for (int i = 0; i < mLen && k > 0; i++)
        {
            if (mainStr[i] == str[j])
            {
                j++;
                if (j == subLen)
                {
                    j = 0;
                    k--;
                }
                if (k == 0)
                {
                    return true;
                }
                continue;
            }
        }
        return false;
    }
    void permuteFunc(vector<int> &alphaFreq, string mainStr, string &tar, string curStr)
    {
        if (curStr.size() > 7)
        {
            return;
        }
        if (strSet.find(curStr) == strSet.end())
        {
            strSet.insert(curStr);
            if (isSubqueue(mainStr, curStr))
            {
                if (curStr.size() > ans.size() || (curStr.size() == ans.size() && curStr > ans))
                {
                    ans = curStr;
                }
            }
        }

        if (curStr.size() >= tar.size())
        {
            return;
        }

        for (int i = 0; i < tar.size(); i++)
        {
            char ch = tar[i];
            if (alphaFreq[ch - 'a'] > 0)
            {
                curStr += tar[i];
                alphaFreq[ch - 'a']--;
                permuteFunc(alphaFreq, mainStr, tar, curStr);
                curStr.pop_back();
                alphaFreq[ch - 'a']++;
            }
        }
    }

public:
    string longestSubsequenceRepeatedK(string s, int k)
    {
        mk = k;
        int n = s.size();
        vector<int> alphaFreq(26);
        for (int i = 0; i < n; i++)
        {
            alphaFreq[s[i] - 'a']++;
        }
        string target;
        for (int i = 25; i >= 0; i--)
        {
            target.insert(target.end(), alphaFreq[i] / k, 'a' + i);
        }
        string curStr;
        permuteFunc(alphaFreq, s, target, curStr);
        return ans;
    }
};

int main()
{
    Solution solution{};
    string s = "bb";
    int k = 2;
    solution.longestSubsequenceRepeatedK(s, k);
    return 0;
}